package com.midea.leetcode;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @description：
 * @author: wangwl23
 * @create: 2021-03-10 16:35
 */
public class DynamicProgram {
    public static void main(String[] args) {
        int fibonacci = fibonacci(20);
        System.out.println(fibonacci);
        int fib = fib(20);
        System.out.println(fib);

        int fib2 = fib2(20);
        System.out.println(fib2);
        int fib3 = fib3(20);
        System.out.println(fib3);
    }
    /**
     * 斐波那契数列
     * 暴力递归
     * @param num
     * @return
     */
    private static int fibonacci(int num) {
        if (num==0 || num==1){
            return num;
        }else{
            return fibonacci(num-1)+fibonacci(num-2);
        }
    }
    /**
     * 带备忘录的递归解法，自上而下
     * @param num
     * @return
     */
    private static int fib (int num){
        int[] res = new int[num+1];
        Arrays.fill(res,0);
        res[1] = 1;
        return helper(res,num);
    }
    private static int helper(int[] res, int num) {
        if(num==1 || num ==2){
            return 1;
        }
        if (res[num] != 0){
            return res[num];
        }
        res[num] = helper(res,num-1)+helper(res,num-2);
        return res[num];
    }

    /**
     * 动态规划，自底向上推算
     * @param num
     * @return
     */
    private static int fib2 (int num){
        int[] dp = new int[num+1];
        Arrays.fill(dp,0);
        dp[1] = dp[2] = 1;
        for (int i=3;i<=num;i++){
            dp[i]= dp[i-1] + dp[i-2];
        }
        return dp[num];
    }

    /**
     * 简化后的动态规划，只需保存之前的两个值即可
     * @param num
     * @return
     */
    private static int fib3(int num){
        int pre = 1;
        int cur = 1;
        for (int i=3;i<=num;i++){
            int sum = pre+cur;
            pre = cur;
            cur = sum;
        }
        return cur;
    }
}
